/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
export var searchMatrix = function (matrix, target) {
  // 先找出应该在哪一行
  let row = bisect(matrix, target, -1, 0)
  if (row === -1) return false
  // 再找出应该在哪一列
  let col = bisect(matrix[row], target, 0, null)

  if (col === -1) return false
  return matrix[row][col] === target
}

function bisect(arr, target, flag = 0, valuePop = null) {
  let left = 0,
    right = arr.length - 1,
    ans = -1
  while (left <= right) {
    const mid = (left + right) >> 1
    const val = valuePop !== null ? arr[mid][valuePop] : arr[mid]
    if (val === target) {
      ans = mid
      if (flag === 0) return mid
      else if (flag === -1) left = mid + 1
      else right = mid - 1
    } else if (val < target) {
      if (flag === -1) ans = mid
      left = mid + 1
    } else {
      if (flag === 1) ans = mid
      right = mid - 1
    }
  }
  return ans
}

/**
 * 一次二分查找
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
export var searchMatrix2 = function (matrix, target) {
  const m = matrix.length,
    n = matrix[0].length
  let low = 0,
    high = m * n - 1
  while (low <= high) {
    const mid = Math.floor((high - low) / 2) + low
    const x = matrix[Math.floor(mid / n)][mid % n]
    if (x < target) {
      low = mid + 1
    } else if (x > target) {
      high = mid - 1
    } else {
      return true
    }
  }
  return false
}
